\documentclass[a4paper,10pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{lscape}
\usepackage{url}
\usepackage[left=2cm,top=3cm,right=2cm,bottom=2cm,head=1.5cm,includefoot]{geometry}
\usepackage{fancyhdr}

\begin{document}
%Caratula
%\maketitle 
%\thispagestyle{empty}

\begin{titlepage}
\thispagestyle{empty}
\begin{center}
\includegraphics[scale=0.3]{./img/logo.jpg}\\
%\large{\textsc{Universidad de Buenos Aires}}\\
\Large Universidad de Buenos Aires\\
\Large{\textsc{Facultad De Ingeniería}}\\
\Large{1\textsuperscript{er} Cuatrimestre 2012}

\vfill

\Huge{\textsc{\textbf{ Trabajo Final}}}

\vfill
\normalsize{\textbf{INTEGRANTES}}\\[3ex]

Zucchiatti, Martín - \textit{85797} \\
\texttt{tanomartin05@gmail.com} \\[2.5ex]
Pereira, María Florencia - \textit{88816} \\
\texttt{ mflorenciapereira@gmail.com } \\[2.5ex]

\vfill
\LARGE{75.70 Sistemas de programación no convencional de Robots} \\
\end{center}
\end{titlepage}


%Cabecera y pie de pagina
\pagestyle{fancy}
\lfoot{\scriptsize{75.70 Sistemas de programación no convencional de Robots\\
Trabajo Final}}
\cfoot{}
\rfoot{\thepage}



\newpage
\begin{abstract}
El objetivo de este trabajo es construir un modelo de algoritmo genético y una red neuronal que permitan resolver el problema de Knapsack multidimensional. Este problema es un ejemplo de problema combinatorio y optimización donde se busca maximizar la cantidad de objetos a seleccionar sin superar un volúmen dado, tratanto de maximizar algún aspecto. Se expone en este informe la soución planteada, los resultados obtenidos y conclusiones.
\end{abstract}


\section{Estado del arte}
En las última década los algoritmos genéticos han recibido un interés particular debido a su facilidad de implementación, robustez de la búsqueda de soluciones y ha sido aplicado en una gran cantidad de campos. Sin embargo, son de especial utilidad cuando se trata de problemas combinatorios como por ejemplo, el problema del viajante, porque son capaces de obtener soluciones satisfactorias en una forma mucho más rápida y simple que con otros métodos.
Los algoritmos genéticos son de probada eficacia en gran cantidad de campos, entre otros, los siguientes:
\begin{itemize}
\item Diseño automatizado de equipamiento industrial.
\item Búsqueda de bugs en programas informaticos.
\item Calibración y detección de daños en estructuras civiles.
\item Diseño de topologías de circuitos impresos.\end{itemize}




En cuanto al problema de Knapsack, es uno de los 21 problemas NP-completos de Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972. Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en un artículo de George Mathews Ballard.
Si bien la formulación del problema es sencilla, su resolución es más compleja. Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un gran tamaño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación.

En particular, para el ámbito de la criptografía es especialmente importante formular los casos donde la resolución no sea simple para poder utilizarlo en encripación con clave pública o asimétricos, como por ejemplo en el criptosistema de Merkle-Hellman.

Asimismo, es común su uso en la asignación de recursos cuando se cuenta con memoria limitada.

Finalmente, en las última décadas las Redes Neuronales Artificiales (ANN) se han aplicado ampliamente a la minería de datos, puesto que ofrece los medios para modelar de manera efectiva y eficiente problemas grandes y complejos. 

\section{Introducción}

\subsection{Algoritmos genéticos}

Los algoritmos genétios simulan la evolución de una población  de individuos, mediante un proceso iterativo aplicando un conjunto de estructuras. Cada estructura esta compuesta de características que definen la aptitud del individuo en el entorno. Las estructuras evolucionan de generación en generación mediante recombinación de sus integrantes, la mutación de algunas características elegidas al azar, y la selección de aquellas estructuras que se mostraron mas aptas.

Cada individuo representa una solución posible al problema dado.

El primer paso de un algoritmo genético es generar una población inicial al azar. Luego cada generación se crea a partir de una generación anterior. Se repite el proceso hasta que algún individuo alcanza la aptitud esperada, se llega a una cota máxima de evaluaciones, o toda la población esta dominada por el mismo individuo.
La selección provee la abstracción del mecanismo de selección natural. Algunos individuos sobreviven directamente en la próxima generación o contribuyen en forma indirecta mediante la cruza.
La cruza abstrae la reproducción sexual en los sistemas naturales.

Como la selección produce un sesgo en la búsqueda que produce la cruza se introduce la mutación, para garantizar la diversidad. Introduce una o mas variaciones en las características de algunos individuos.


\subsubsection{Métodos de Selección}

\paragraph{Selección por Ruleta}
Se construye una ruleta particionada en ranuras de igual tamaño, las cuales se enumeran. A cada individuo se le asigna una cantidad de ranuras, proporcional a su aptitud. La probabilidad de escoger una ranura es uniforme, lo que hace que los individuos de mayor aptitud, tengan más probabilidad de contribuir a las siguientes generaciones, aunque no esta garantizado. 

\paragraph{Selección con Control sobre el número Esperado}
Asegura que todos los individuos con aptitud superior a la media, tenga una copia para el siguiente paso del algoritmo, es decir para la cruza. A diferencia del anterior, que no esta asegurado que los queden copias de los mejores individuos.

\paragraph{Selección Elitista}
Los métodos anteriores no garantizan la preservación de los mejores individuos, ya que pueden no ser seleccionados o ser reemplazados por sus hijos durante la cruza. La selección elitista soluciona este problema, preservando los mejores m individuos generados para la siguiente iteración, es decir, se tiene en cuenta en la siguiente generación.


\subsubsection{Métodos de Cruza}

\paragraph{Cruza Simple}
Elige al azar un punto de cruza. Luego se intercambian los segmentos de cromosoma separados por este punto.

\paragraph{Cruza Multipunto}
Se elige n puntos de cruza en forma aleatoria y se intercambian las porciones de cromosomas definidas entre cada par de puntos. El caso anterior es un caso particular de este, con n = 1.

\paragraph{Cruza Binomial}
Se puede generar un único hijo o dos. Determina para cada punto, en forma aleatoria, si sobrevive el gen del padre o de la madre.


\subsubsection{Métodos de Mutación}

Mantiene la diversidad de la población, disminuyendo el riesgo de convergencia prematura o la obtención de óptimos locales.

\paragraph{Mutación Simple}
Elige en forma aleatoria un gen, el cual se muta con cierta probabilidad, habitualmente muy baja. La probabilidad de mutación se mantiene constante durante las sucesivas generaciones.

\paragraph{Mutación Adaptativa por Convergencia}
La probabilidad de mutación varía en base al grado de convergencia de la población. Empieza con una probabilidad de mutación baja, y aumente o disminuye en función de la evolución de la población, aprovechando la información histórica, a diferencia de la anterior.

\paragraph{Mutación Adaptativa por Temperatura}
Es independiente de la información genética. De plantea una probabilidad mínima y máxima de mutación. Se parte de un valor inicial de probabilidad, y se actualiza en base al tiempo o cantidad de generaciones, aumentando o disminuyendo la probabilidad de mutación.

\subsection{Redes neuronales}

Las redes neuronales intentan reproducir el comportamiento del cerebro.
Constan de dispositivos elementales de proceso (neuronas). Un conjunto de ellas pueden representar un número, una letra, etc.

Existen 3 tipos de neuronas:
\begin{itemize}
\item Las que reciben estímulos externos del sistema.
\item Las que procesan la información recibida y generan una representación interna (unidades ocultas). No tienen relación con la entrada y la salida del sistema.
\item Las que emiten una respuesta fuera del sistema.\end{itemize}


Si llamamos yi a la señal de salida de la neurona i-esima cuando esta llega a la unidad j-esima ha sufrido transformaciones intermedias debido a su paso por otras neuronas formando la entrada total Netj:

		Netj = SUM( yi wij)  donde la suma incrementa “i” y wij es el peso de cada unidad.

		
		\begin{figure}[h!]
\centering
\includegraphics[scale=.5]{./img/img1.png}
\end{figure}


Existen 2 formas de actualizar el estado de una neurona:
\begin{itemize}
\item Asincrónico: la neurona evalúa su estado a medida que llega la información en forma independiente.
\item Sincrónico: la información llega en forma continua pero el cambio se realiza simultáneamente (como activado por un reloj interno).
\end{itemize}



Los estados de activación de la red se modelan como un vector A(t) = (a1(t), ..., aN(t)).

El estado de activación de una neurona esta fuertemente relacionado con la interacción de la unidad con sus vecinas y la señal que envía la neurona.

La conexión entre neuronas i-j (sinapsis) esta ponderada por un peso wij. Se considera por simplicidad que el efecto de cada señal es aditivo de forma tal que la entrada que recibe una unidad (potencial postsináptico) Netj es la suma del producto de cada señal individual por el valor de la sinapsis que conecta.



\subsubsection{Función de Transferencia o Activación}

La suma de las entradas de una neurona pasan por esta función para generar una salida:
	
		$ yi(t) = f (Neti(t)) $

		
		

		
				$Y(t) = [ f (Net1(t)) , ...., f (Netn(t)) ]$
		
Debido a que esta función no esta centrada en la unidad, se llama a a dicho desplazamiento y representa el umbral de activación.

	$yi(t+1) = f(Neti – ai) = f(SUM(wij yi(t)) – ai) $
	
	

	$wi(t+1) = wi(t) + b [d(t) – y(t)] xi(t)$

	
Exiten 4 funciones de Activación:
\begin{itemize}
\item Funciones Escalón: Se utiliza en neuronas binarias (fáciles de modelar por hard pero muy acotadas). Si la suma de las entradas es mayor que un umbral la activación es 1. Si es menor la activación es 0 o –1.

\item Función lineal y mixta: la función responde a f(x)=x. Si la función es mayor que un límite la activación es 1, si es menor que un límite inferior es 0 o –1 y si esta entre ambos límites entonces la activación se define como una función lineal de la suma de entradas.

\item Función continua: 
Función de transferencia gaussiana:  Los centros y anchura de la función se adaptan. Cuando tenemos dos niveles ocultos utilizamos esta función.
				\end{itemize}

				
\subsubsection{Niveles o Capas}

Las neuronas se ubican en capas (de entrada, Ocultas y de salida).
Se dice que una red es totalmente conectada si todas las salidas de un nivel llegan a todos los nodos del nivel siguiente.

Las neuronas se conectan hacia delante cuando las salidas pueden ser conectadas como entradas de neuronas de niveles siguientes.
Se dice conectadas hacia atrás cuando se conectan a niveles previos. 
Si existen lazos cerrados tenemos sistemas recurrentes.


\subsection{Características de las RN}

Se caracterizan por su topología, mecanismo de aprendizaje, tipo de asociación de información entre entrada - salida y forma de representación de la misma.
\\
\\
\textbf{Topología:} Redes monocapa, Redes Multicapas con conexiones hacia delante (no permiten conexiones laterales y se utilizan en el reconocimiento de patrones), Redes Multicapas con conexiones hacia delante y hacia atrás (aceptan conexiones laterales o conexiones autorrecurrentes)
\\
\\
\textbf{Mecanismo de Aprendizaje:} Mecanismo por el cual una red modifica sus pesos en función de información de entrada. Implica creación, destrucción o modificación de conexiones entre neuronas.
Una red ha aprendido cuando sus pesos se estabilizan.
Los criterios aplicados para el aprendizaje se denominan  regla de aprendizaje. Existen reglas que responden a un aprendizaje supervisado y otras a uno no supervisado.
Otro criterio sería el aprendizaje on line y off line (fase de aprendizaje y luego pruebas).
\\
\\
Las redes con aprendizaje supervisado pueden dividirse en: Aprendizaje por corrección de errores, por refuerzo y estocásticos.
Por corrección de errores es off-line y lo que hace es ajustar los pesos de la red en función de la diferencia entre la salida real y la esperada. Un ejemplo de esta red es el Perceptrón, pero este último solo evalúa errores locales. Se han desarrollado nuevos algoritmos para contemplar el error medio.
En aprendizaje por refuerzo mas que un tutor existe un crítico que evalúa 1 o –1 en función de éxito o fracaso de la salida. Es un aprendizaje on line.
En el aprendizaje estocástico se introducen cambios aleatorios en los pesos de las conexiones y evaluar su efecto a partir del objetivo deseado y de distribuciones de probabilidades. Es off line.

Las redes con aprendizaje  no supervisado no requieren influencia externa para modificar el peso de sus conexiones.
Existen dos tipos, el aprendizaje Hebbiano y el aprendizaje Competitivo y Cooperativo.
En el aprendizaje Hebbiano se ajustan los pesos de las conexiones de acuerdo con la correlación de los valores de activación de las neuronas conectadas.
En el competitivo y cooperativo las neuronas compiten y cooperan para llevar a cabo una tarea.
El objetivo es categorizar los datos que se introducen en la red. De esta forma, las informaciones similares se clasifican formando parte de la misma categoría y activan la misma neurona de salida.


\subsubsection{Perceptron}

Varias neuronas de entrada y una de salida. Solo procesa 2 estados de salida.
Su algoritmo de aprendizaje es supervisado y por corrección de errores (off-line).
\\
\\
	$Y = f( w1 x1 + w2 x2 – 1 a)$
\\

Primero se presentan los valores de los pesos y el umbral.
Se presenta el par entrada y salida esperada.
Calculo Y.
Adapto los pesos en función de la salida:
\\
\\
	$wi(t+1) = wi(t) + b [d(t) – y(t)] xi(t)$
\\
\\
Solo resuelve problemas linealmente separables.
En el caso de un robot con 4 sensores podríamos tener todas las combinaciones en memoria y actuar en función de ello, pero sería muy caro. Entonces se utiliza una RN del tipo Perceptron entrenada con un número representativo de patrones y aprender el comportamiento del sistema.


\subsubsection{Backpropagation}
Es un algoritmo que se aplica a redes de mas de 2 capas. Se alimenta la red con un par de entrada salida y se calcula el término de error de cada neurona hasta llegar a la salida. A continuación se propaga el error hacia atrás ajustando los pesos.
En este algoritmo se encuentra un valor mínimo de error mediante la aplicación de pasos descendentes. El problema es que el proceso puede detenerse en un mínimo local. Esto no es un problema si consideramos que la solución no siempre es un mínimo global sino cualquiera que sea menor a un valor preestablecido.
Para controlar la convergencia se debe trabajar con saltos chicos aunque esto hace que el algoritmo sea mas lento.

\section{Problema a resolver}

Como se mencionó anteriormente el problema de Knapsack es un problema de optimización combinacional. Su enunciado es el siguiente:

Dado un conjunto de items, cada uno con su peso, se busca determinar el número de cada item a incluir en una colección de forma tal que el peso total sea menor o igual a un límite dado. El volúmen deberá ser lo más grande posible, así como la cantidad de items a incluir.

Asimismo, se puede hacer que el problema sea multidimensional si se agregan condiciones de optimización adicionales. En este caso, se asignará a cada item un volúmen, un costo y un valor de utilidad. Con estos valores, se bucará:

\begin{itemize}
\item Minimizar la cantidad de items
\item Minimizar el costo total
\item Maximizar la utilidad total
\end{itemize}

El problema es NP-completo, con lo cual no puede resolverse correctamente en un tiempo menor al polinómico. Asimismo es NP-hard, lo que significa que no hay un algoritmo que indique en tiempo polinómico si es óptimo. También existe un algoritmo de aproximación para obtener una solución del problema.

\section{Solución propuesta}

Para implementar un algoritmo genético que permita solucionar el problema de Knapsack se utilizó la herramienta JGAP.
JGAP es un framework para modelar algoritmos genéticos. Contiene clases que permiten crear, definir las características de la población e individuos, hacerla evolucionar, evaluar una función de aptitud y luego realizar una selección, mutación o cruza. 

Se evaluarán 2 métodos de solución del problema. El primero resuelve el problema clásico, el segundo es una solución al problema de Knapsack multidimensional.


\subsection{Implementación}

\subsubsection{Archivo inicial}
El programa recibe como parámetros el volúmen máximo que pueden ocupar los items y la ubicación de un archivo que contiene los items, con el siguiente formato:

\begin{verbatim}
nombre_del_item:volumen_que_ocupa:costo:utilidad\end{verbatim} 

El archivo se procesa y se cargan los items en cuatro arrays que contienen los nombres, volúmenes, costos y utilidad de los items ingresados.

Se define un volúmen máximo de  1000000000.0 el volúmen deberá estar entre 1 y este número.



\begin{verbatim}
public static final double MAX_BOUND = 1000000000.0d;\end{verbatim} 




\subsubsection{Mutación}
Se agrega mutación con un mutationrate constante (esto significa que en promedio se mutarán 1/mutationrate individuos), con la siguiente línea:

    \begin{verbatim}
conf.addGeneticOperator(new MutationOperator(conf, mutationRate));    \end{verbatim} 




\subsubsection{Cruza}

Se tomará para este ejemplo la cruza por default, “Cruza Simple”.


\subsubsection{Selección}


Dadas las características del problema a resolver, se elige preservar a los mejores individuos, usando selección elitista. Por esta razón se indica a la aplicación que deberá utilizarse una selección elitista, mediante el siguiente código:

    \begin{verbatim}
conf.setPreservFittestIndividual(true); //salva al individuo más apto.    \end{verbatim} 

De esta manera los mejores individuos se preservarán para la siguiente iteración.



\subsection{Configuración del algoritmo y evolución de la población}
La generación de estos genes se realiza con el siguiente código:

    \begin{verbatim}
Gene[] genesEjemplo = new Gene[itemVolumes.length];
    for (int i = 0; i < itemVolumes.length; i++) {
      genesEjemplo[i] = new IntegerGene(conf, 0,                                    
      (int) Math.ceil(volumenmaximo itemVolumes[i]));
    }    \end{verbatim} 

\begin{verbatim}
IChromosome cromosomaexjemplo = new Chromosome(conf, genesEjemplo);
    conf.setSampleChromosome(cromosomaexjemplo);\end{verbatim} 

En la línea anterior se generan tantos genes como items hay inicialmente. La clase IntegerGene representa los genes descriptos anteriormente y permite especificar cantidades mínimas (0) y máximas de cada item (volumen ingresado/total de items).


Finalmente, se indica al objeto de configuración cuántos cromosomas tendrá la población. A más cromosomas, mayor potencial de soluciones a encontrar pero mayor será el tiempo de evolución de la población, también.

\begin{verbatim}
conf.setPopulationSize(50);\end{verbatim} 

Para crear la población inicial se crean individuos al azar. También se intenta usar un archivo previo en caso de que exista.


   \begin{verbatim}
 Genotype poblacion;
    try {
      Document doc = XMLManager.readFile(new File("knapsackPrevio.xml"));
      poblacion = XMLManager.getGenotypeFromDocument(conf, doc);
    }
    catch (FileNotFoundException fex) {
      poblacion = Genotype.randomInitialGenotype(conf);
    }
    poblacion = Genotype.randomInitialGenotype(conf);                                                     \end{verbatim} 


Finalmente se hace evolucionar a la población mediante el siguiente código:

\begin{verbatim}

    for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
      population.evolve();
    }     \end{verbatim} 

Con un máximo de 150 evoluciones, utilizando la función de aptitud que se describe en la siguiente sección. Se obtiene al individuo más apto con la siguiente línea de código.

  \begin{verbatim}
IChromosome mejorSolucion = population.getFittestChromosome();  \end{verbatim} 

\subsection{Modelo y función de aptitud}
Cada cromosoma o individuo tendrá tantos genes como items haya. Los alelos serán, entonces, valores enteros que representan cuántos items de ese tipo se tienen para ese cromosoma. 


Se asgina una función de aptitud a la configuración.
Para implementar esta función se extiende la clase de JGAP FitnessFunction. Esta clase se usa para determinar qué tan óptima es una solución particular en relación a otras soluciones. Dado un cromosoma para evaluar, deberá devolver su valor de aptitud, a mayor valor, más apto el cromosoma.
Se redefinió el método evaluate() para evaluar qué tan cerca está el valor del objetivo ingresado. 

\subsubsection{Función KnapsackFitnessFunction (método 1)}


En un primer paso se considera cuánto difiere el volumen de la solución (la suma de los volúmenes de todos los items que contiene) con el ingresado por el usuario y se asigna un valor de aptitud mayor a los que tengan una menor diferencia. Si la diferencia fuera 0, se asigna el máximo valor de aptitud dado que la solución es exacta.

En un segundo paso, se modifica el valor para que se considere una mejor aptitud aquella solución con menor cantidad de items. El valor obtenido en el paso 1 se divide por una penalización basada en la cantida de items. A más items, más alta la penalización y por tanto, menor el valor de apitud. 

\subsubsection{Función KnapsackNNFitnessFunction (método 2)}

La modificación al problema original propuesta en este informe busca resolver el problema de knapsack multidimensional, que implica, además de buscar la menor diferencia de volúmen, agrega condiciones de optimización adicionales.

Para solucionar este problema, se propone usar una red neuronal que aprenda a partir de un set como se clasificarán las soluciones presentadas (en un preprocesamiento), luego utilizar la misma para clasificar las soluciones obtenidas y modificar el resultado de la función de aptitud en función de este valor. El proceso realizado puede resumirse en la siguiente imágen.




\begin{figure}[h!]
\centering
\includegraphics[scale=.5]{./img/img2.png}
\end{figure}


La creación y el entrenamiento de la red se realizará utilizando la herramienta Weka.

Se construye un archivo arff con el siguiente formato:
\begin{verbatim}

@ATTRIBUTE cantidad	REAL

@ATTRIBUTE costo 	REAL

@ATTRIBUTE utilidad 	REAL

@ATTRIBUTE class 	{1,2,3,4,5}\end{verbatim} 

Para cada solución del training set, estos atributos indican una instancia y cómo fue clasificada la misma. Esto es, una solución que contiene la cantidad de items especificada en “cantidad”, un costo total de “costo” y una utilidad total de “utilidad” se clasificará con un valor entre 1 y 5 (indicado en el atributo “class”).
En base a este training set se construye una red Perceptrón Multicapa con valores por default:

 \begin{verbatim}
-L <learning rate> : 0.3
 -M <momentum>: 0.2.
 -N <number of epochs> : 500.
 -V <percentage size of validation set> : 0.
 -S <seed> : 0.
 -E <threshold for number of consequetive errors> : 20. \end{verbatim} 
 
Se eligió trabajar con el perceptrón multicapa porque es una red feed forward simple que se utiliza para clasificación y aprendizaje supervisado.
La red fue entrenada usando corrección de errores con regla delta generalizada por ser común su uso con la red Perceptrón.
Con la red construida, al hacer evolucionar la población, se creará una instancia que represente a la solución o cromosoma de la siguiente manera:
    
\begin{verbatim}
    Instance instance = new Instance(5);
	instance.setDataset(inst);
	instance.setValue(0, numberOfItems);
	instance.setValue(1, this.getTotalCost(a_subject));
	instance.setValue(2, this.getTotalUtility(a_subject));\end{verbatim} 

Finalmente, se clasificará la instancia con \begin{verbatim}
classif.classifyInstance(instance)                                            \end{verbatim} que arrojará el factor por el que se multiplicará la diferencia de volumen para obtener el valor de aptitud de la solución.




\section{Resultados}
Como caso de prueba se ingresa el archivo de items con los siguientes valores:

\begin{verbatim}
linterna:50.2:20:10

comida:14.8:5:10

radio:27.5:50:2

television:6800.0:400:4

celular:25.0:300:4

lapiz:4.75:10:2

libro:95.36:20:5

gps:1500.7:40:7

carpa:18365.9:80:9

heladera:83571.1:1000:11
\end{verbatim} 
Asimismo, se especifica un volúmen de 1000.


\subsection{Knapsack simple}
Se ejecutó la aplicación 5 veces, usando solamente el algoritmo genético para obtener soluciones al problema de knapsack simple.

Las soluciones obtenidas se resumen en el cuadro 1.
\\
Vemos que las soluciones obtenidas son satisfactorias, el error más grande fue de 0.123 \%. Sin embargo, no se obtuvo el óptimo (que no es garantizado por los algoritmos genéticos).

\subsection{Knapsack multidimensional}
Se ingresó un archivo arff con valores de entrenamiento de la red, con la estructura mencionada anteriormente y valores acordes a los objetivos del problema.
Las soluciones obtenidas se resumen en el cuadro 2.

Las soluciones obtenidas fueron satisfactorias nuevamente. 
Observamos que el error es bajo en la mayoría de los casos. 
Los costos y la utilidad son aproximadamente constantes también. Vemos que los elementos con menor costo y más utilidad son aquellos cuya cantidad es mayor (cumpliendo los objetivos planteados).


\begin{landscape}

\centering     % optional, probably makes it look better to have it centered on the page

\begin{table}[htbp]
\caption{}
\small
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}
\hline
\multicolumn{1}{|l|}{Solucion} & \multicolumn{1}{l|}{linterna} & \multicolumn{1}{l|}{comida} & \multicolumn{1}{l|}{radio} & \multicolumn{1}{l|}{televisión} & \multicolumn{1}{l|}{celular} & \multicolumn{1}{l|}{lápiz} & \multicolumn{1}{l|}{libro} & \multicolumn{1}{l|}{gps} & \multicolumn{1}{l|}{carpa} & \multicolumn{1}{l|}{heladera} & \multicolumn{1}{l|}{total items} & \multicolumn{1}{l|}{total volumen} & \multicolumn{1}{l|}{diferencia} & \multicolumn{1}{l|}{Error \%} \\ \hline
1 & 136 & 325 & 197 & 5 & 534 & 55 & 132 & 3 & 1 & 0 & 1388 & 100121.47 & -121.47 & -0.12147 \\ \hline
2 & 469 & 494 & 58 & 3 & 25 & 16 & 189 & 19 & 0 & 0 & 1273 & 100087.34 & -87.34 & -0.08734 \\ \hline
3 & 48 & 13 & 451 & 5 & 8 & 20 & 146 & 0 & 2 & 0 & 693 & 99953.86 & 46.14 & 0.04614 \\ \hline
4 & 13 & 262 & 76 & 1 & 259 & 24 & 13 & 28 & 2 & 0 & 678 & 100000.28 & -0.28 & -0.00028 \\ \hline
5 & 223 & 477 & 78 & 0 & 13 & 273 & 23 & 26 & 2 & 0 & 1115 & 99964.23 & 35.77 & 0.03577 \\ \hline
\end{tabular}
\label{}
\end{table}


\begin{table}[htbp]

\caption{}

\footnotesize
\scalebox{0.95}{
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}

\hline
\multicolumn{1}{|l|}{Solucion} & \multicolumn{1}{l|}{linterna} & \multicolumn{1}{l|}{comida} & \multicolumn{1}{l|}{radio} & \multicolumn{1}{l|}{televisión} & \multicolumn{1}{l|}{celular} & \multicolumn{1}{l|}{lápiz} & \multicolumn{1}{l|}{libro} & \multicolumn{1}{l|}{gps} & \multicolumn{1}{l|}{carpa} & \multicolumn{1}{l|}{heladera} & \multicolumn{1}{l|}{total items} & \multicolumn{1}{l|}{total costo} & \multicolumn{1}{l|}{total utilidad} & \multicolumn{1}{l|}{total volumen} & \multicolumn{1}{l|}{diferencia} & \multicolumn{1}{l|}{Error \%} \\ \hline
1 & 43 & 1020 & 627 & 4 & 1026 & 380 & 35 & 5 & 0 & 0 & 3140 & 351410 & 16974 & 99993.2 & 6.8 & 0.0068 \\ \hline
2 & 390 & 344 & 5 & 1 & 933 & 1085 & 387 & 2 & 0 & 0 & 3147 & 308740 & 15205 & 99991.16 & 8.84 & 0.00884 \\ \hline
3 & 168 & 1465 & 788 & 1 & 20 & 419 & 298 & 7 & 0 & 0 & 3166 & 66915 & 20367 & 99998.03 & 1.97 & 0.00197 \\ \hline
4 & 240 & 1643 & 185 & 2 & 742 & 107 & 4 & 17 & 0 & 0 & 2940 & 247495 & 22529 & 100003.48 & -3.48 & -0.00348 \\ \hline
5 & 420 & 554 & 1309 & 1 & 60 & 457 & 97 & 10 & 0 & 0 & 2908 & 101930 & 14071 & 100008.37 & -8.37 & -0.00837 \\ \hline
\end{tabular}
}
\label{}
\end{table}



\end{landscape}




\newpage


\section{Conclusión}

Los problemas de decisión muchas veces involucran varios objetivos o atributos conflictivos. El problema de knapsack, la selección de una combinación óptima de items, es un modelo de problema de decisión clásico con un único objetivo y restricción. Es posible extender este modelo, de forma tal que se planteen varios objetivos y restricciones cuatitativas. En este informe, se propone método de resolución donde múltiples atributos cuantitativos y cualitativos deberán conformar una única solución.
Asimismo, integra los dominios de redes neuronales y algoritmos genéticos en un mismo problema.

La red neruonal se utilizó para ponderar la solución o cromosoma obtenido, a partir de un training set dado que luego influye en la función de aptitud del algoritmo genético. 
El número de soluciones posibles es amplio. Con los algoritmos genéticos es posible explorar el espacio de soluciones eficientemente y con redes neuronales se procede a la clasificación de la solución obtenida. 

Los resultados obtenidos fueron satisfactorios en la mayoria de los casos, sin embargo, como se planteo desde el principio, son aproximaciones y no es posible garantizar una solución óptima. 

\pagebreak
\begin{thebibliography}{99}
(1) Richard M. Karp Reducibility Among Combinatorial Problems.
\\
\\
(2) G.B. Mathews, On the partition of numbers.
\\
\\
(3) Ghazanfari. Using neural networks and genetic algorithms to solve a multiple attributes knapsack problem.
\\
\\
(4) Vladimir Golovko. A Neural Network for Combinatorial Problems of Optimization.
\\
\\
(5) Fonseca. An overview of evolutionary algorithms in multi-objective optimization.
\\
\\
(6) Hwang. Multiple attribute decision-making.
\\
\\
(7) Holland. Adaptation in natural and artificial systems.
\\
\\
(8) García Martinez, Servente, Pasquini. Sistemas Inteligentes.


\end{thebibliography}








\end{document}
